package DataStructure.linear;


import java.util.Iterator;

//链表
public class LinkList<T> implements Iterable<T>{
    //记录头结点
    private Node head;

    //记录链表的长度
    private int N;



    //结点类
    private class Node{
        //存储数据
        T item;
        //下一个结点
        Node next;

        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }

    //初始化方法
    public LinkList(){
        //初始化头结点
        this.head=new Node(null,null);
        //初始化元素个数
        this.N=0;
    }

    //清空链表
    public void clear(){
        head.next=null;
        this.N=0;
    }

    //获取链表长度
    public int length(){return N;}

    //判断链表是否为空
    public boolean isEmpty(){return N==0;}

    //获取指定位置的元素
    public T get(int i){
        //通过循环从头结点开始往后找，依次找I次
        Node n = head.next;
        for (int index = 0; index < i; index++) {
            n=n.next;
        }
        return n.item;
    }

    //向链表中添加元素t
    public void insert(T t){
        //找到当前最后一个节点
        Node n=head;
        while (n.next!=null){
            n=n.next;
        }
        //创建一个新节点
        Node newNode = new Node(t,null);
        //让当前最后一个节点指向新节点
        n.next=newNode;
        //让元素的个数加一
        N++;
    }

    //向指定位置添加元素
    public void insert(int i,T t){
        //找到前一个节点
        Node pre=head;
        while (i-->0){
            pre=pre.next;
        }
        //找到i位置的节点
        Node curr = pre.next;
        //创建新节点
        Node newNode = new Node(t,curr);
        //让前一个节点指向新节点
        pre.next=newNode;
        //元素个数加一
        N++;
    }

    //删除指定位置的元素并返回
    public T remove(int i){
        //找到i的前一个节点
        Node pre=head;
        for (int index = 0; index <=i-1; index++) {
            pre=pre.next;
        }
        Node curr= pre.next;
        pre.next=curr.next;//跳过中间的节点直接指向下一个节点
        N--;
        return curr.item;
    }

    //查找t元素第一次出现的位置
    public int indexOf(T t){
        Node n=head;
        for (int index = 0; n.next!=null; index++) {
            n=n.next;
            if(n.item.equals(t)){
                return index;
            }
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n=head;
        }
        @Override
        public boolean hasNext(){
            return n.next!=null;
        }
        @Override
        public Object next(){
            n=n.next;
            return n.item;
        }
    }

    //翻转整个链表
    public void reverse(){
        if(isEmpty()){
            return;
        }
        reverse(head.next);
    }

    //翻转指定节点并返回
    public Node reverse(Node curr){
        if(curr.next==null){
            head.next=curr;
            return curr;
        }
        //递归的翻转当前节点的下一个节点,返回值就是链表翻转后当前节点的上一个节点
        Node pre = reverse(curr.next);
        //让返回的节点的下一个节点变为当前节点curr
        pre.next=curr;
        //吧当前节点的下一个节点变为null
        curr.next=null;
        return curr;
    }
}
